package com.base.bitoperation;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 397. 整数替换
 *给定一个正整数n ，你可以做如下操作：
 *
 * 如果n是偶数，则用n / 2替换n 。
 * 如果n是奇数，则可以用n + 1或n - 1替换n 。
 * n变为 1 所需的最小替换次数是多少？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-replacement
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年11月19日 11:04
 */
public class IntegerReplacement {
    Map<Integer,Integer> map = new HashMap<>();
    {
        map.put(1,0);
    }

    public int integerReplacement(int n) {
        if(map.containsKey(n)){
            return map.get(n);
        }
        //    if(n==1){
        //        return 0;
        //    }
        int tmp = 0;
        if(n%2==0){
            tmp =  1+integerReplacement(n/2);
        }else{
            tmp =  2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1));

        }
        map.put(n,tmp);
        return tmp;

    }

    public static void main(String[] args) {
        System.out.println(new IntegerReplacement().integerReplacement(65535));
    }
}
